package 快速排序;

import java.util.Arrays;
import java.util.Stack;

public class 非递归实现快排 {
    public static void quickSort(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        int start=0;
        int end=arr.length-1;

        int pivot=partition(arr,start,end);

        //对左区间是否入栈进行判断
        if (pivot-1>start) {
            stack.push(0);//low先进
            stack.push(pivot-1);
        }
        //对右区间是否入栈进行判断
        if (pivot+1<end) {
            stack.push(pivot+1);//low先进
            stack.push(end);
        }

        while (!stack.isEmpty()) {
            end = stack.pop();
            start =stack.pop();

            pivot=partition(arr,start,end);

            //对左区间是否入栈进行判断,区间内起码要有两个元素才能入栈
            if (pivot-1>start) {
                stack.push(0);//low先进
                stack.push(pivot-1);
            }
            //对右区间是否入栈进行判断
            if (pivot+1<end) {
                stack.push(pivot+1);//low先进
                stack.push(end);
            }

        }

    }

    public static int partition(int[] arr,int low,int high) {
        //high 用来找比基准值小的
        //low  用来找比基准值大的
        int tmp=arr[low];
        while (low<high) {
            while (low<high && arr[high]>=tmp) {
                high--;
            }
            arr[low]=arr[high];//比基准值小的往前放

            while (low<high && arr[low]<=tmp) {
                low++;
            }
            arr[high]=arr[low];//比基准值大的往后放
        }
        arr[low]=tmp;
        return low;
    }

    public static void main(String[] args) {
        int[] arr={12,5,9,34,6,8,33,56,89,0,7,4,22,55,77};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));

    }
}
